Toggle navigation
Home
About
About Journal
Historical Evolution
Indexed In
Awards
Reference Index
Editorial Board
Journal Online
Archive
Project Articles
Most Download Articles
Most Read Articles
Instruction
Contribution Column
Author Guidelines
Template
FAQ
Copyright Agreement
Expenses
Academic Integrity
Contact
Contact Us
Location Map
Subscription
Advertisement
中文
Journals
Publication Years
Keywords
Search within results
(((LIU Xuejing[Author]) AND 1[Journal]) AND year[Order])
AND
OR
NOT
Title
Author
Institution
Keyword
Abstract
PACS
DOI
Please wait a minute...
For Selected:
Download Citations
EndNote
Ris
BibTeX
Toggle Thumbnails
Select
Differential crow search algorithm based on Lévy flight for solving discount {0-1} knapsack problem
LIU Xuejing, HE Yichao, LU Fengjia, WU Congcong, CAI Xiufeng
Journal of Computer Applications 2018, 38 (
2
): 433-442. DOI:
10.11772/j.issn.1001-9081.2017071852
Abstract
(
499
)
PDF
(1349KB)(
385
)
Knowledge map
Save
A large-scale Discount {0-1} Knapsack Problem (D{0-1} KP) is difficult to solve with the deterministic algorithms, thus a differential crow search algorithm based on Lévy flight named LDECSA was proposed. Firstly, the coding problem about the second mathematical model of D{0-1} KP was solved by using mixed coding. Secondly, a New greedy Repair and Optimization Algorithm (NROA) was used to deal with the infeasible solution. Thirdly, in order to avoid the problems of local optimum and slow convergence, Lévy flight and differential strategy were introduced. Finally, the reasonable value of awareness probability and flight length were determined through experiments, the differential strategy was also chosen. The experimental results on four types of large-scale D{0-1} KP show that LDECSA is very suitable for solving large-scale D{0-1} KP with very satisfactory approximate solution.
Reference
|
Related Articles
|
Metrics
Select
Chaotic crow search algorithm based on differential evolution strategy for solving discount {0-1} knapsack problem
LIU Xuejing, HE Yichao, LU Fengjia, WU Congcong, CAI Xiufeng
Journal of Computer Applications 2018, 38 (
1
): 137-145. DOI:
10.11772/j.issn.1001-9081.2017061445
Abstract
(
480
)
PDF
(1387KB)(
367
)
Knowledge map
Save
In Discount {0-1} Knapsack Problem (D{0-1}KP), the weight coefficients and the value coefficients in a large range, are difficult to solve by deterministic algorithms. To solve this problem, a Chaotic Crow Search Algorithm based on Differential Evolution strategy (DECCSA) was proposed. Firstly, the initial crow population was generated by chaotic mapping. Secondly, mixed coding and Greedy Repair and Optimization Strategy (GROS) were used to solve the coding problem of D{0-1}KP. Finally, Difference Evolution (DE) strategy was introduced to improve the convergence rate of the algorithm. The experimental results on four large-scale D{0-1}KP instances show that DECCSA is better than Genetic Algorithm (GA), bacterial foraging optimization algorithm, and mutated bat algorithm, and it can get the optimal solution or approximate optimal solution. It's very suitable for solving D{0-1}KP.
Reference
|
Related Articles
|
Metrics
Select
Mutated bat algorithm for solving discounted {0-1} knapsack problem
WU Congcong, HE Yichao, CHEN Yiying, LIU Xuejing, CAI Xiufeng
Journal of Computer Applications 2017, 37 (
5
): 1292-1299. DOI:
10.11772/j.issn.1001-9081.2017.05.1292
Abstract
(
517
)
PDF
(1156KB)(
532
)
Knowledge map
Save
Since the deterministic algorithms are difficult to solve the Discounted {0-1} Knapsack Problem (D{0-1}KP) with large-scale and wide data range, a Mutated Double codes Binary Bat Algorithm (MDBBA) was proposed. Firstly, the coding problem of D{0-1} KP was solved by double coding. Secondly, the Greedy Repair and Optimization Algorithm (GROA) was applied to the individual fitness calculation of bats, and the algorithm was quickly and effectively solved. Then, the mutation strategy in Differential Evolution (DE) was selected to improve the global optimization ability. Finally, Lévy flight was carried out by the bat individual according to certain probability to enhance the ability of the algorithm to explore and jump out of local extrema. Simulation was tested on four large-scale instances. The result shows that MDBBA is very suitable for solving large-scale D {0-1} KP, which has better optimal value and mean value than FirEGA (First Genetic Algorithm) algorithm and Double Binary Bat Algorithm (DBBA), and MDBBA converges significantly faster than DBBA.
Reference
|
Related Articles
|
Metrics